This invention relates to switching networks and more particularly to multipath switching networks that include means for overcoming faults.
Multistage interconnection networks have long been studied for use in telephone switching and multiprocessor systems. Since the early 70's, several such networks have been proposed to meet the communication needs of multiprocessor systems in a cost-effective manner. They are typically designed for N-inputs and N-outputs, where N is a power of an integer n, such as 2, and contain log.sub.n N stages. The switches in adjacent stages are interconnected to permit the establishment of a path from any input of the network to any output of the network. These multistage networks have many properties that make them attractive for switching systems. One such property is their relatively low rate of increase in complexity and cost as the number of inputs and outputs increases. Generally their size and cost increase on the order of N log.sub.n N, as compared to crossbar switches where size and cost increase on the order of N.sup.2. Another such property is the ability to provide up to N simultaneous connections through path lengths on the order of log.sub.n N. Still another property is the ability to employ simple distributed algorithms that make a routing controller unnecessary. One example of such a network is found in U.S. Pat. No. 4,516,238 issued to Huang et al. on May 7, 1985.
Multistage networks with log N stages also have two other properties which are not desirable; i.e., only one path exists from any input to any output, and distinct input/output paths have common links. These properties lead to two disadvantages. First, an input/output connection may be blocked by a previously established connection even if the inputs (sources) and the outputs (destinations) of the network are distinct. Second, the failure of even a single link or switch disables several input/output connections. The former leads to poor performance in a random connections environment, and the latter leads to a lack of fault tolerance and concomitant low reliability.
The performance degradation due to blocking and the decrease in reliability due to lack of fault tolerance become increasingly serious with the size of the network, because the number of paths passing through a given link increase linearly with N. Fortunately, it turns out that the addition of a few links per stage results in a substantial increase in the number of multiple paths between every network input and network output pair, and that ameliorates the disadvantages. Such networks are called multiple path multistage networks. In setting up a connection, multiple path multistage interconnection networks allow an alternate path to be chosen where conflicts arise from a blocking situation or when faults develop in the network. This provides for both better performance and higher reliability than that which is offered by the unique path multistage networks.
To better understand the principles of the invention described below, it may be useful to have a particular multiple path multistage network in mind. To that end, the following describes the augmented shuffle exchange network described in "Augmented Shuffle-Exchange Multistage Interconnection Networks", V. P. Kumar and S. M. Reddy, Computer, Jun. 1987, pp. 30-40. FIG. 6 of the article is reproduced here as FIG. 1 to aid in explaining the network. The augmented shuffle exchange network of FIG. 1 is still a blocking network, but the probability of blocking is reduced because of the multiple paths that are included. This feature is illustrated in the description below.
FIG. 1 presents a five stage network with 16 inputs and outputs. The stage numbers are shown in the bottom of the drawing. The switches in stages 1 and 2 each have two inputs at the left of the switch, one input at the top of the switch, two outputs at the right of the switch, and one output at the bottom of the switch. The switches at stage 3 of FIG. 1 only have two inputs and two outputs, each. When the inputs at the top of the switches and the outputs at the bottom of the switches are not considered (in stages 2 and 3), the three center stages of FIG. 1 simply depict a portion of a conventional shuffle exchange network. The connections of the top inputs in the switches of stages 2 and 3 with the bottom outputs of the switches in those stages form the additional, alternate, routing paths for the network. For example, if inputs 11 and 13 of switch 10 wish to be connected to network outputs 0 and 4 respectively, switch 10 can be set to connect input 11 to output 12, switch 20 can be set to connect input 12 to output 22, switch 30 can be set to connect input 22 to output 32, and switch 40 can be set to apply input 32 to output 0 of the network. Connecting input 13 to output 15 in switch 10 would not be useful because, as shown by FIG. 1, the link connected to output 15 cannot reach output 4 of the network. Therefore, input 13 must be connected within switch 10 to the alternate routing output of the switch; to wit, output 14. Output 14 of switch 10 is connected to the top input of switch 16. From output 14, the signal of input 13 may then be routed to switch 26 through switch 16, then to switch 36, to switch 46, and finally to output 4 of the network. Thus, the alternate routing inputs and outputs of the switches in the stages 1 and 2 of FIG. 1 together the links that connect them provide for an alternate path in the network.
It may be noted that FIG. 1 also includes stage 0 and stage 4 which are somewhat different in kind from the center three stages. Specifically, stage 0 comprises two-input/one-output multiplexer switches, and stage 4 comprises one-input/two-outputs multiplexer stages. In stage 0, each switch i derives its input signals from inputs i and ##EQU1## of the network. Thus, switch i where i=0 (i.e., switch 50) derives its inputs from the network's input 0 and input 8, switch i where i=2 (i.e., switch 51) derives its inputs from the network's input 2 and input 10, etc. In stage 4, the switches are arranged in groups of four. The first and third switches in the top group connect to the network's output 0, and output 1, and the second and fourth switches connect to the network's output 2 and output 3. The next group of four switches connect to the network's outputs 4-7, etc.
The reliability and performance improvement obtained from a multipath network depend on how effectively the available alternate paths are used by the routing algorithm. One can use a back-tracking routing algorithm that exhaustively searches for an available fault-free path. However, implementation of back-tracking is relatively expensive in terms of hardware, and back-tracking can take an inordinately long time to set up connections. Non back-tracking algorithms, therefore, are much preferred. One such algorithm is described in the aforementioned Kumar et al. paper. The algorithm assumes that each switch is able to ascertain whether it is faulty in any one of its three outputs. If a faulty condition is discovered, the switch is able to communicate that information, through its inputs, to the switches to which it is connected.
The overall algorithm results from each switch performing a specified routing task. Each switch in the network has buffers at each of its three inputs. The buffers store incoming packet signals and in instances of contention, when alternate routing is not possible (such as when all three inputs have incoming pockets), the buffers store the packets so that no information is lost. Of course, the packet signals considered here are the conventional packet signals which contain a header section and a data section. The header section contains different types of information, including the source address, the destination address, parity, etc. In operation, each switch looks at the destination addresses of the packets that it receives for routing at each of the three inputs. The packets are then switched to the appropriate outputs (the two outputs on the right of the switch) based on the destination addresses of the packets in the buffers. If more than one packet is desirous of connection to a particular switch output, or if access to one of the required switch outputs is blocked by a fault in the switch, then the packet is switched to the auxiliary output of the switch (bottom output).
It may be noted that in stage 0, at the very input of the network, if access to one of the switches is blocked due to a fault, the packet at that switch is routed to another switch. It may also be noted that stage 3 switches, such as switch 36, do not have a top input and a bottom output shown. For purposes of the routing task, it may be assumed that those switches are identical to the switches in stages 1 and 2 but the bottom output tied to a faulty state.
The FIG. 1 network is described above in connection with packet switching. The same network is also described in connection with circuit switching in a PhD dissertation by V. P. Kumar, titled "On Highly Reliable High-Performance Multistage Interconnection Networks", University of Iowa, 1985. The switches described in the thesis have a modular design: there is an "input module" at each input of the switch and an "output module" at each output of the switch, for a total of six separate modules. Each input module is connected to each output module through a set of nine linking buses. Each module in the thesis switch is a state machine that implements the protocol functions in setting up a connection. The design presented employs an encoding arrangement for both the control and the data signals. The encoding employs the class of M-out-of-N codes for the control signals, for which TSC (Totally Self-Checking) checkers exist. For the data signals, the Berger code (which is also a TSC checkable code) is employed. The combinational logic portion of the modules is implemented using a single fault secure PLA (Programmable Logic Array). Each input module has a 1-to-3 demultiplexer for switching to each of the three outputs, and each output modules, in turn, has a 3-to-1 multiplexer which enables it to select from each of the three inputs. The control signals for the multiplexers and demultiplexers are generated by the control PLA. Finally, each module has an arrangement of TSC checkers that detect errors in the data lines as well as in the control paths.
The switch design described above is quite good, but it does have a number of problems. Specifically, any "line stuck-at" faults from the control PLA to the multiplexers and demultiplexers can cause corruption and/or misrouting of data. These failures can go undetected. Also, an error detected by a TSC checker in the data lines at an input module cannot be definitively pinpointed. It can be due to a fault in the preceding stage or in the current stage, and there is no way of distinguishing between these two possibilities. In short, the problems combine to make the switch not fully effective for the purpose of fault-tolerant operation.